package 回溯;

import java.util.LinkedList;
import java.util.List;

public class _216_组合总和III {
    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] arr = new int[]{1,2,3,4,5,6,7,8,9};
        List<Integer> temp = new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();
        backtrack(arr, temp, res, n, k, 0, 0);
        return res;
    }

    private void backtrack(int[] arr, List<Integer> temp, List<List<Integer>> res, int n, int k, int level, int start) {
        if (n <= 0 || level == k) {
            if (n == 0 && level == k) {
                res.add(new LinkedList<>(temp));
            }
            return;
        }

        for (int i = start; i < arr.length; i++) {
            if (temp.contains(arr[i])) continue;
            temp.add(arr[i]);
            backtrack(arr, temp, res, n - arr[i],k,level + 1, i + 1);
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        _216_组合总和III o = new _216_组合总和III();
        List<List<Integer>> lists = o.combinationSum3(3, 9);
    }
}
